/*
 * @lc app=leetcode.cn id=62 lang=cpp
 *
 * [62] 不同路径
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    int uniquePaths(int m, int n) {
        //使用排列组合c(m+n-2,n-1)会有溢出问题，所以需要用动态规划
        /**
         *? 我们令 dp[i][j] 是到达 i, j 最多路径
         *? 动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
         *? 注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1
         */
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};
// @lc code=end

